#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:

	TreeNode* _Convert(TreeNode* root, TreeNode* parent)
	{
		if (root->left)
		{
			root->left = _Convert(root->left, root);
		}

		if (root->right)
		{
			_Convert(root->right, root)->left = root;
		}

		if (parent != nullptr && parent->left == root && root->right != nullptr)
			return root->right;

		if (parent != nullptr && parent->right == root && root->left != nullptr)
			return root->left;

		return root;
	}



	TreeNode* Convert(TreeNode* pRootOfTree)
	{
		if (pRootOfTree == nullptr)
			return nullptr;

		TreeNode* end = pRootOfTree;
		while (end->right)
		{
			end = end->right;
		}

		_Convert(pRootOfTree, nullptr);

		TreeNode* fast = end->left;
		TreeNode* slow = end;

		while (fast)
		{
			fast->right = slow;
			fast = fast->left;
			slow = slow->left;
		}

		return slow;
	}
};